package sf.sort;

public class ShellSort implements Sort{

    // 希尔排序
    // 策略是索引差以n的倍数所有的数进行插入排序
    // 然后逐步减少N
    // 比插入排序好的地方是

    @Override
    public void sort(int[] unsorted) {
        for (int i = unsorted.length / 2; i >= 1; i = i / 2) {
            for (int i1 = 0; i1 < i; i1++) {
                hillSort(unsorted, i1, i);
            }
        }
    }

    public void hillSort(int[] nums, int i, int n) {
        for (int j = i+n; j < nums.length; j+=n) {
            int temp = nums[j];
            int k = j;
            for (;k > i && nums[k - n] > temp;k -= n) {// 这个最后一轮是基本上是有序的，所以循环很快就结束
                nums[k] = nums[k - n];
            }
            nums[k] = temp;
        }
    }


}
